package org.aplombh.java.interview.newcoder;

public class NC17_最长回文子串 {
    public static void main(String[] args) {
        System.out.println(new NC17_最长回文子串().getLongestPalindrome("baabccc"));
        System.out.println(new NC17_最长回文子串().getLongestPalindromeDP("baabccc"));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param A string字符串
     * @return int整型
     */
    public int getLongestPalindrome(String A) {

        if (A.length() < 2) return A.length();

        int res = 0;
        int n = A.length();
        char[] a = A.toCharArray();

        for (int i = 0; i < n; i++) {
            int y1 = solve(a, i, i);
            int y2 = solve(a, i, i + 1);
            res = Math.max(res, y1);
            res = Math.max(res, y2);
        }
        return res;
    }

    private int solve(char[] a, int i, int j) {
        while (i >= 0 && j < a.length) {
            if (a[i] != a[j]) break;
            i--;
            j++;
        }
        return j - i - 1;
    }

    public int getLongestPalindromeDP(String A) {
        int res = 1;
        int n = A.length();
        char[] a = A.toCharArray();
        boolean[][] f = new boolean[n][n];

        // 不能直接双重for循环，得通过长度去循环
        for (int len = 0; len < n; len++) {
            for (int k = 0; k < n - len; k++) {
                int i = k;
                int j = k + len;

                if (a[i] == a[j]) {
                    if (i == j || i + 1 == j) f[i][j] = true;
                    else f[i][j] = f[i + 1][j - 1];
                    if (f[i][j]) res = Math.max(res, j - i + 1);
                }
            }
        }
        return res;
    }
}